#include<iostream>
#include<vector>
#include<queue>
using namespace std;

class ListNode{
public:
    int val;
    ListNode *next;
};

//2.两数相加
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){
    ListNode *cur1 = l1, *cur2 = l2;
    //创建新链表的头节点
    ListNode *newhead = new ListNode(0);
    ListNode *cur3 = newhead;

    //变量t表示进位
    int t = 0;
    while(cur1||cur2||t){
        if(cur1){
            t += cur1->val;
            cur1 = cur1->next;
        }
        if(cur2){
            t += cur2->val;
            cur2 = cur2->next;
        }
        cur3->next = new ListNode(t % 10);
        t /= 10;
        cur3 = cur3->next;
    }

    //返回新链表的第一个节点，删除头节点
    ListNode *newlist = newhead->next;
    delete newhead;
    newhead = nullptr;

    return newlist;
}


//24.两两交换链表中的节点
ListNode* swapPairs(ListNode* head){
    if(head==nullptr||head->next==nullptr){
        return head;
    }
    //创建一个头节点
    ListNode *newhead = new ListNode(0);

    ListNode *cur = head;
    ListNode *prev = newhead;

    while(cur&&cur->next){
        ListNode *next = cur->next;
        cur->next = next->next;
        next->next = cur;
        prev->next = next;

        prev = cur;
        cur = cur->next;
    }

    //删除头节点
    head=newhead->next;
    delete newhead;
    newhead = nullptr;

    return head;
}

//143.重排链表
//逆序链表
ListNode* ReverseList(ListNode* head){
    ListNode *prev = nullptr;
    ListNode *cur = head;
    while(cur){
        ListNode *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}
void reorderList(ListNode* head){
    //先排除特殊情况
    if(head==nullptr||head->next==nullptr||head->next->next==nullptr){
        return;
    }
    //先找到中间节点
    ListNode *slow = head, *fast = head;
    while(fast&&fast->next){
        fast = fast->next->next;
        slow = slow->next;
    }

    //从中间节点的下一个节点开始逆序后面的节点,并将前半部分链表断开
    ListNode *cur2 = ReverseList(slow->next);
    slow->next = nullptr;
    ListNode *cur1 = head;

    //依次合并两个链表
    ListNode *newhead = new ListNode(0);
    ListNode *cur3 = newhead;
    int n = 1;
    while(cur1&&cur2){
        if(n%2==1){
            cur3->next = cur1;
            cur1 = cur1->next;
        }
        if(n%2==0){
            cur3->next = cur2;
            cur2 = cur2->next;
        }
        n++;
        cur3 = cur3->next;
    }
    if(cur1){
        cur3->next = cur1;
    }
    if(cur2){
        cur3->next = cur2;
    }

    //删除头节点
    head = newhead->next;
    delete newhead;
    newhead = nullptr;
}

//合并k个升序链表
//解法一：
//创建仿函数实现小堆的功能
struct cmp{
    bool operator()(const ListNode* l1,const ListNode* l2){
        return l1->val > l2->val;
    }
};
ListNode* mergeKLists(vector<ListNode*>& lists){
    //创建一个小根堆
    //模板参数第一个表示的是存放的数据类型，第二个表示的是适配器，第三个表示的是仿函数，建堆规则
    priority_queue<ListNode *, vector<ListNode *>, cmp> heap;

    //先将所有链表的不为空的头节点存放到堆中
    for(auto node : lists){
        if(node){
            heap.push(node);
        }
    }

    //合并k个升序链表
    ListNode *newhead = new ListNode(0);
    ListNode *cur = newhead;

    while(!heap.empty()){
        //循环取出堆顶的节点，从堆中删除
        ListNode *tmp = heap.top();
        heap.pop();
        //将取出的节点链接在链表后面
        cur->next = tmp;
        cur = cur->next;
        //如果取出的节点的下一个节点不为空，存放到堆中
        if(tmp->next){
            heap.push(tmp->next);
        }
    }

    //删除头节点
    ListNode *head = newhead->next;
    delete newhead;
    newhead=nullptr;

    return head;
}
//解法二：
//分治归并
ListNode* merge(vector<ListNode*>& lists,int left,int right){
    if(left>=right){
        return lists[left];
    }

    //取中间链表的头节点下标
    int mid = left + (right - left) / 2;
    //递归左右子区间
    ListNode *l1 = merge(lists, left, mid);
    ListNode *l2 = merge(lists, mid + 1, right);

    ListNode *newhead = new ListNode(0);
    ListNode *cur1 = l1, *cur2 = l2, *cur3 = newhead;
    while(cur1&&cur2){
        if(cur1->val<cur->val){
            cur3->next = cur1;
            cur1 = cur1->next;
        }
        else{
            cur3->next = cur2;
            cur2 = cur2->next;
        }
        cur3 = cur3->next;
    }
    if(cur1){
        cur3->next = cur1;
    }
    if(cur2){
        cur3->next = cur2;
    }

    //删除头节点返回
    ListNode *head=newhead->next;
    delete newhead;
    newhead = nullptr;

    return head;
}
ListNode* mergeKLists(vector<ListNode*>& lists){
    //如果数组为空，直接返回空节点
    if(lists.empty()){
        return nullptr;
    }
    return merge(lists, 0, lists.size() - 1);
}


//k个一组翻转链表
//逆序函数
ListNode* reverse(ListNode* head,int k){
    //先标记子链表的第一个节点，逆序后就变成了最后一个节点
    ListNode *tmp = head;
    ListNode *prev=nullptr;
    ListNode *cur = head;
    while(cur&&k--){
        ListNode *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }

    //将逆序后的子链表与后面的剩余节点链接起来
    tmp->next = cur;
    //返回逆序后的第一个节点
    return prev;
}
ListNode* reverseKGroup(ListNode* head, int k){
    //给链表增加一个头节点
    ListNode *newhead=new ListNode(0);
    newhead->next = head;
    ListNode *prev = newhead;

    //先统计链表有多少个节点
    int n = 0;
    ListNode *cur = head;
    while(cur){
        n++;
        cur = cur->next;
    }

    //用节点总数除以一组节点个数计算需要逆序多少个子链表
    n /= k;
    cur = head;
    while(n--){
        //新链表的头节点链接子链表逆序后返回的第一个节点
        prev->next = reverse(cur, k);
        //后移到逆序后的最后一个节点
        prev = cur;
        cur = cur->next;
    }

    //删除头节点
    head=newhead->next;
    delete newhead;
    newhead=nullptr;

    return head;
}

int main(){

    return 0;
}